package QuickSort;

public class QuickSort {

    //这是取左边的 注意中间 与左边不一样
    public static void quickSort(int nums[],int l,int r)
    {
        if(l>=r)
            return;

        int mid=nums[l];
        int i=l-1,j=r+1;
        while(i<j)
        {
            while(nums[++i]<mid);
            while (nums[--j]>mid);
            if(i<j)
            {
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }
        }
        quickSort(nums,l,j);
        quickSort(nums,j+1,r);
    }

    //这是处于中间 的 记忆 处于中间的 处于中间的时候  必须取<= 使得 i j分开
    //然后i刚刚处于大于那一块  j刚刚处于小于那一块
    //l j
    //i r
    public static void quickSortMid(int nums[],int l,int r)
    {
        if(l>=r)
            return;

        int mid=nums[(l+r)/2];
        int i=l-1,j=r+1;
        while(i<=j)
        {
            while(i<=j&&nums[++i]<mid);
            while (i<=j&&nums[--j]>mid);
            if(i<=j)
            {
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
            }
        }
        quickSortMid(nums,l,j);
        quickSortMid(nums,i,r);
    }

    public static void quickSortNormal(int nums[],int l,int r)
    {
        if(l>=r)
            return;

        int mid=nums[r];
        int i=l,j=r;
        while(i<j)
        {
            while(nums[i]<mid)++i;
            if(i<j)
            {
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
                //位移是防止相同的出现
                --j;
            }
            while (nums[j]>mid)--j;
            if(i<j)
            {
                int tmp=nums[i];
                nums[i]=nums[j];
                nums[j]=tmp;
                //位移是防止相同的出现
                ++i;
            }
        }
        System.out.println(i+" "+j);
        quickSortNormal(nums,l,i-1);
        quickSortNormal(nums,j+1,r);
    }
}
